博主内推：阿里菜鸟网络春招 【部门直推】【海量实习岗位&正式岗位】
一、选择题
1.算法分析中，记号O表示（B），记号Ω标售（A）,记号Θ表示（D）
A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界
2.以下关于渐进记号的性质是正确的有：（A）
A f(n) =Θ(g(n)),g(n) =Θ(h(n)) ⇒f(n) =Θ(h(n))
B f(n) =O(g(n)),g(n) =O(h(n)) ⇒h(n) =O(f(n))
C O(f(n))+O(g(n)) = O(min{f(n),g(n)})
D f(n) = O(g(n)) ⇔g(n) = O(f(n))
3. 记号O的定义正确的是（A）。
A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }；
B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤ f(n) }；
C O(g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }；
4. 记号Ω的定义正确的是（B）。
A O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ f(n) ≤ cg(n) }；
B O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n≥n0有：0≤ cg(n) ≤ f(n) }；
C (g(n)) = { f(n) | 对于任何正常数c>0，存在正数和n0 >0使得对所有n≥n0有：0 ≤f(n)0，存在正数和n0 >0使得对所有n≥n0有：0 ≤cg(n) < f(n) }；
5. T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是( C )
A T（n）= T（n – 1）+1，T（1）=1
B T（n）= 2n2
C T（n）= T（n/2）+1，T（1）=1
D T（n）= 3nlog2n
6. 动态规划算法的基本要素为（C）
A 最优子结构性质与贪心选择性质
B 重叠子问题性质与贪心选择性质
C 最优子结构性质与重叠子问题性质
D 预排序与递归调用
7.下列不是动态规划算法基本步骤的是（ A ）。
A 找出最优解的性质 B 构造最优解
C 算出最优解 D 定义最优解
8.能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）
A 最优子结构性质与贪心选择性质
B 重叠子问题性质与贪心选择性质
C 最优子结构性质与重叠子问题性质
D 预排序与递归调用
9.下面是贪心算法的基本要素的是（ C ）。
A 重叠子问题 B 构造最优解 C 贪心选择性质 D 定义最优解
10（ D ）是贪心算法与动态规划算法的共同点。
A 重叠子问题 B 构造最优解
C 贪心选择性质 D 最优子结构性质
11.使用分治法求解不需要满足的条件是（A ）。
A 子问题必须是一样的 B 子问题不能够重复
C 子问题的解可以合并 D 原问题和子问题使用相同的方法解
12.实现循环赛日程表利用的算法是（ A ）。
A 分治策略 B 动态规划法
C 贪心法 D 回溯法
13.使用分治法求解不需要满足的条件是（A ）。
A 子问题必须是一样的 B 子问题不能够重复
C 子问题的解可以合并 D 原问题和子问题使用相同的方法解
14.下列算法中不能解决0/1背包问题的是（A ）
A 贪心法 B 动态规划 C 回溯法 D 分支限界法
15.以下( C )不能不能在线性时间完成排序
A 计数排序 B 基数排序 C 堆排序 D 桶排序
16.下列哪一种算法是随机化算法（ D ）
A 贪心算法 B 回溯法 C 动态规划算法 D 舍伍德算法
17. 下列算法中通常以自底向上的方式求解最优解的（ B ）。 A 分治法 B 动态规划法 C 贪心法 D 回溯法
18. n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 ( A ) 说法不正确？A
A 让水桶大的人先打水，可以使得每个人排队时间之和最小
B 让水桶小的人先打水，可以使得每个人排队时间之和最小
C 让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水
D 若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样
19.哈弗曼编码的贪心算法所需的计算时间为 ( B )。
A O(n2n) B O(nlogn) C O(2n) D O(n)
20.下面关于NP问题说法正确的是(B )
A NP问题都是不可能解决的问题
B P类问题包含在NP类问题中
C NP完全问题是P类问题的子集
D NP类问题包含在P类问题中
21.背包问题贪心算法所需的计算时间为( B )
A O(n2n) B O(nlogn) C O(2n) D O(n)
22.背包问题的回溯算法所需的计算时间为（ A ）
A O(n2n) B O(nlogn) C O(2n) D O(n)
23.采用最大效益优先搜索方式的算法是（ A ）
A 分支界限发 B 动态规划法 C 贪心法 D 回溯法
24. 在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨牌的个数是 （ A ）
A ( 4k – 1）/3 B 2k /3 C 4k D 2k
25. 下列随机算法中运行时有时候成功有时候失败的是（C ）
A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法
26. 实现大整数的乘法是利用的算法（ C ）。
A 贪心法 B 动态规划法 C 分治策略 D 回溯法
二、填空题
1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。
2.矩阵连乘问题的算法可由 动态规划 设计实现。
3.从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。
4.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。
5.快速排序算法的性能取决于 划分的对称性 。
6.使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（ 1 ），在最坏情况下，搜索的时间复杂性为O（ logn ）。
三、解答题
1. 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。 写出二分搜索的算法，并分析其时间复杂度
2. 分析最有搜索二叉树和0/1背包的时间复杂度
3. 试用动态规划算法实现最大子矩阵和问题：求n×m矩阵A的一个子矩阵，使其各元素之各为最大
4已知输入向量a=（1,3,4，-2），给出用FFT的蝶形操作求输出向量y的结果，并分析出FFT的计算时间复杂度。
1.采用递归算法求递归方程F(n)=F(n-1(+F(n-2)，算法描述如下（就是递归fibonacci！）
问：算法共需要进行多少次递归调用（算法中没引用F(i)一次称为一次递归调用）。有没有更好的算法来计算F(n)?若有请描述算法并分析复杂度。
2.如下算法是否产生平均分布的随即置换？为什么？
Permute-With-All(A)
n←length(A)
for i←1 to n
swap(A[i],A[RANDOM(1,n)])
注：RANDOM(1,n)随机、等可能地返回整数k，1≤k≤n
3. 能否在给定的s[n]中判断是否存在两个数的和为x，并且时间复杂度是nlgn，如果可以写出程序的伪代码，否则给出理由。
6. 活动选择问题
（1）递归的时间复杂度分析
（2）动态规划的时间复杂度分析
（3）写出一个更优的算法，并且对其进行时间复杂度分析
7. 多项式乘法问题
描述一个高效的算法来解决复数之间的多项式乘法，多项式的系数为复数，未知数也为复数。
并且对此进行时间复杂度分析。
郑55 算法2013考试题
填空：
给一系列的函数，根据渐进性，从大到小排列n^3/2,nlgn,lgn,e^n,n!,n^2动归的两个性质贪心的两个性质1）NP问题： 2）P问题面试问题 雇一个人的概率： ，雇n个人的概率：复杂度分为： 和 ；动归是牺牲 复杂度换取 复杂度使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（ 1 ），在最坏情况下，搜索的时间复杂性为O（ logn ）。选择：
1摊还排序是（）情况下的（）代价
A最优B最坏C平均D最好
2动态规划的设计思想是a
(a)自底向上 (b)自上而下 (c)从左向右 (d)从右向左
3贪心算法的设计思想是b
(a)自底向上 (b)自上而下 (c)从左向右 (d)从右向左
4以下哪一个更可能描述实际一个有效的算法d
(a) (b) (c) (d)
5蝶形操作的设计思想是a
(a)分治法 (b)贪心算法 (c)动态规划 (d)回溯
6以下哪一个不是NPC问题
(a)单源最短路径 (b)巡回售货员问题 (c)布尔可满足性问题 (d)大数分解
7以下哪个不是几何研究中的基本操作
(a)+ (b)— (c)× (d)/
8哪个问题不能用贪心算法解决
(a)活动安排 (b)哈夫曼编码 (c)分数背包 (d)0-1背包
9哪个问题不能用动态规划解决c
(a)分数背包 (b)0-1背包 (c)最长简单路径 (d)最短简单路径
10插入排序的最好时间复杂度是a
(a)n (b)n^2 (c)nlgn (d)lgn
11归并排序的时间复杂度是c
(a)n (b)n^2 (c)nlgn (d)lgn
12算法分析中，记号O表示（B），记号Ω标售（A）,记号Θ表示（D）
A 渐进下界 B 渐进上界 C 非紧上界 D 紧渐进界 E 非紧下界
13.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水，水流恒定。如下 ( A ) 说法不正确？A
A 让水桶大的人先打水，可以使得每个人排队时间之和最小
B 让水桶小的人先打水，可以使得每个人排队时间之和最小
C 让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水
D 若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样
14.哈弗曼编码的贪心算法所需的计算时间为 ( B )。
A O(n2n) B O(nlogn) C O(2n) D O(n)
15.下面关于NP问题说法正确的是(B )
A NP问题都是不可能解决的问题
B P类问题包含在NP类问题中
C NP完全问题是P类问题的子集
D NP类问题包含在P类问题中
大题
四路归并排序：分解时分成四个，合并等其他步骤与二路归并相似，请写出核心算法，并分析时间复杂度。矩阵链乘积的递归算法T（n）= 1 n=1
n>=2
请详细分析该算法的时间复杂度
给出最优二叉搜索树的程序代码和p，q概率根据概率1）求e,w,root，2）画出二叉树的结构3）请说出root[i,j]有什么意义
（见3621大班试卷影印版的第五题）
FFt蝶形操作 见3621大班试卷的影印版第九题字符串自动机构造，见书
2006-2007学年第二学期《计算机算法设计与分析》试题
院系：软件学院专业：软件工程年级：2004级
一．简答题（共10分）
略
二．计算题（35分）
１．(6分) 对下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n))。
(1) f(n)=3n，g(n)=2n
(2) f(n)=log n + 5，g(n)=log n2
(3) f(n)=log n，g(n)=
答：
(1) f(n) = Ω(g(n)) (2分)
(2) f(n) = θ(g(n)) (2分)
(3) f(n) = O(g(n)) (2分)
2．（８分）采用动态规划策略，计算a=｛5,-3,7,-4,-5,9,-2,10,-3,2｝的最大子段和，并给出这个最大子段和的起始下标和终止下标。［设数组a中的元素下标从１开始。］要求给出过程。
答：
b[1]=5；
b[2]=max{b[1]+a[2]，a[2]}=max{2,-3}=2
b[3]=max{b[2]+a[3]，a[3]}=max{9,7}=9
b[4]=max{b[3]+a[4]，a[4]}=max{5,-4}=5
b[5]=max{b[4]+a[5]，a[5]}=max{0,-5}=0
b[6]=max{b[5]+a[6]，a[6]}=max{9,9}=9
b[7]=max{b[6]+a[7]，a[7]}=max{7,-2}=7
b[8]=max{b[7]+a[8]，a[8]}=max{17,10}=17
b[9]=max{b[8]+a[9]，a[9]}=max{14,-3}=14
b[10]=max{b[9]+a[10]，a[10]}=max{16,2}=16
(上述每两行１分，共５分)
最大子段和为17（1分）
（若数组下标从１开始）起始下标：６（１分），终止下标：８（１分）
（若数组下标从０开始）起始下标：５（0.5分），终止下标：7（0.5分）
３．（11分）设有３件工作分配给３个人，将工作i分配给第j个人所花的费用为Cij，现将为每一个人都分配１件不同的工作，并使总费用达到最小。设：
要求：
（1）画出该问题的解空间树；（６分）
（2）写出该问题的剪枝策略(限界条件)；（1分）
（3）按回溯法搜索解空间树，并利用剪枝策略对应该剪掉的子树打´；（２分）
（4）最终给出该问题的最优值和最优解。（２分）
答：
（1）
1 2 3
2 3 1 3 1 2
1 1 2 2 3 3
3 2 3 1 2 1
16 16 9 9 9 9
╳ ╳ ╳ ╳
（每个分枝1分，或者是每层2分，共6分）
（2）当耗费大于等于当前最优值时，剪枝。（1分）
（3）见上图。（每2个╳ 1分，共2分）
（4）最优值： 9 （1分）
最优解：2，1，3
４．（８分）给定两个序列X=，Y=，请采用动态规划策略求出其最长公共子序列。要求给出过程。
答：
j 0 1 2 3 4 5
i yi B D C A B
0 xi 0 0 0 0 0 0
1 A 0 0 0 0 1 1
2 B 0 1 1 1 1 2
3 C 0 1 1 2 2 2
4 B 0 1 1 2 2 3
5 Ａ 0 1 2 2 2 3
（上述表内每一行一分，共６分）
最长公共子序列为（２分）
5．（2分）考虑n=3时的0-1背包问题的实例：W={15,10,10}，P={50,30,30}，c=20。当x[1]=1，x[2]=0时，请计算Bound(2)。
答：
Bound(3)=50+5/10 * 20 = 65 (2分)
三、算法填空题（共10分，每空2分）
给定n种物品和一个背包，物品i的重量是w[i], 其价值是p[i], 背包的容量为c。设物品已按单位重量价值递减的次序排序。每种物品不可以装入背包多次，但可以装入部分的物品i。求解背包问题的贪心算法如下：
float Knapsack (float x[ ], float w[ ], float p[ ],float c, int n)
{ float maxsum= ; // maxsum表示装进包的物品价值总和
for ( int i=1;i0) {x[i]=c/w[i]; ;}
return maxsum;
}
答：(共５个空，每空2分，总计10分)
０
int i=1；i